﻿#include<bits/stdc++.h>
using namespace std;

/*
*   题目描述：
* 
	给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

	子数组是数组中的一个连续部分。
*/

class Solution {
    static const int N = 1e5 + 10;
    //int dp[N];
public:
    int maxSubArray(vector<int>& nums) {
        // dp[0] = nums[0];
        // int ret = nums[0], n = nums.size();
        // for(int i = 1; i < n; ++i)
        // {
        //     dp[i] = max(dp[i - 1] + nums[i], nums[i]);
        //     ret = max(ret, dp[i]);
        // }
        // return ret;

        // 空间压缩
         int ret = nums[0], n = nums.size(), dp = nums[0];
         for(int i = 1; i < n; ++i)
         {
             dp = max(dp + nums[i], nums[i]);
             ret = max(ret, dp);
         }
         return ret;


        // 扩展问题：同时记录最大子数组的左右边界
        //int ret = nums[0], dp = nums[0], left = 0, right = 0, n = nums.size();
        //for (int l = 1, r = 1; r < n; ++r)
        //{
        //    if (dp + nums[i] > nums[i]) dp += nums[i];
        //    else l = r, dp = nums[i];
        //    if (dp > ret)
        //    {
        //        ret = dp;
        //        left = l;
        //        right = r;
        //    }
        //}
        //return ret;
    }
};